import java.util.Stack;

import static java.util.Collections.swap;

public class TestSort {
    public static void main(String[] args) {
        int[] arr = {1, 20, 8, 30, 10, 99, 12};
        TestSort testSort = new TestSort();
//        testSort.insertSort(arr);
//        testSort.shellSort(arr);
//        testSort.selectSort2(arr);
//       testSort.heapSort(arr);
//        testSort.bubbleSort(arr);
//        testSort.quickSort(arr);
//        testSort.mergeSort(arr);
        testSort.mergeSortNor(arr);
    }

    /*
     *直接插入排序
     */
    public void insertSort(int[] array) {
        int tmp = 0;
        for (int i = 1; i < array.length - 1; i++) {
            tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /*
     *希尔排序
     */
    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 2;
            shell(array, gap);
        }
    }

    private void shell(int[] array, int gap) {
        int tmp = 0;
        for (int i = gap; i < array.length; i++) {
            tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (tmp < array[j]) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    /*
     *选择排序
     */
    public void selectSort1(int[] array) {
        int minIndex = 0;
        for (int i = 0; i < array.length; i++) {
            minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;
        }
    }

    public void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        int len = array.length;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left; i < len; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array, left, minIndex);
            left++;
            swap(array, right, maxIndex);
            right--;
            len--;
        }

    }

    public void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    /*
     *堆排序
     */
    public void heapSort(int[] array) {
        //创建堆
        createHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }
    }

    public void createHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    public void shiftDown(int[] array, int parent, int length) {
        int child = parent * 2 + 1;
        while (child < length) {
            //如果孩子存在，找到左右孩子中较小的孩子，用child标记
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if (array[parent] <= array[child]) {
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    /*
     *冒泡排序
     */
    public void bubbleSort(int[] array) {
        boolean flag = true;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    /*
     *快速排序
     */
    public void quickSort(int[] array) {
        quickNor(array, 0, array.length - 1);
    }

    public void quickNor(int[] array, int start, int end) {
        Stack<Integer> stack = new Stack<>();
        int pivot = partition2(array, start, end);
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition2(array, start, end);
            if (pivot > start + 1) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if (pivot < end - 1) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    public void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
//        int midIndex=getNumber(array,start,end);
//        swap(array,start,midIndex);

        if (end - start + 1 <= 10) {
            insertSortRange(array, start, end);
            return;
        }
        int pivot = partition(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    private void insertSortRange(int[] array, int start, int end) {
        int tmp = 0;
        for (int i = start + 1; i <= end; i++) {
            tmp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                if (tmp < array[j]) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    private int getNumber(int[] array, int left, int right) {

        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    /*
     *Hoare法
     */
    private int partition(int[] array, int left, int right) {
        int flag = left;
        while (left < right) {
            while (left < right && array[right] >= array[flag]) {
                right--;
            }
            while (left < right && array[left] <= array[flag]) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, left, flag);
        return left;
    }

    /*
     *挖坑法
     */
    private int partition2(int[] array, int left, int right) {
        int flag = array[left];
        while (left < right) {
            while (left < right && array[right] >= flag) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= flag) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = flag;
        return left;
    }

    /*
     *前后指针法
     */
    private int partition3(int[] array, int left, int right) {
        int prev = left;
        int cur = prev + 1;
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, prev, cur);
            }
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }

    /*
     *归并排序
     */
    public void mergeSort(int[] nums) {
        mergeSortSplit(nums, 0, nums.length - 1);
    }

    private void mergeSortSplit(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        //分解
        int mid = (left + right) / 2;
        mergeSortSplit(nums, left, mid-1);
        mergeSortSplit(nums, mid + 1, right);
        //合并
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int k=0;
        int s1=left;
        int s2=mid + 1;
        while(s1<=mid&&s2<=right){
            if(nums[s1]<=nums[s2]){
                tmp[k++]=nums[s1++];
            }else{
                tmp[k++]=nums[s2++];
            }
        }
        while(s1<=mid){
            tmp[k++]=nums[s1++];
        }
        while(s2<=right){
            tmp[k++]=nums[s2++];
        }
        for(int i=left; i<k; i++){
            nums[i]=tmp[i];
        }
    }
    public void mergeSortNor(int[] array){
        int gap=1;
        while(gap<array.length){
            for(int i=0;i<array.length;i=i+gap*2){
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
}
